package 前缀和;

import java.util.HashMap;
import java.util.Map;

public class 和为K的子数组5 {
    //https://leetcode.cn/problems/subarray-sum-equals-k/description/
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,1); // 如果没有额外遇到 正常不越界和为0的区间，每次加的都是1，如果有遇到，就有额外加上正常不越界和为0区间的个数
        // sum = k,自己整的区间和就是k，自己整的就是结果 但往前减区间得不到的
        int sum = 0, ret = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            ret += map.getOrDefault(sum - k,0); // 往前找区间 使得两区间差为 k区间
            map.put(sum,map.getOrDefault(sum,0) + 1);
        }
        return ret;
    }
}
